import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/1 21:27
 * @description Dijkstra算法 + 更新路径，注意每一次更新到最短路径时，路径数需要重置，若相等则路径相加再取模
 */
public class Solution {
    public static void main(String[] args) {
        int[][] roads = {{3,0,4},{0,2,3},{1,2,2},{4,1,3},{2,5,5},{2,3,1},{0,4,1},{2,4,6},{4,3,1}};
        Solution solution = new Solution();
        solution.countPaths(6, roads);
    }
    public int countPaths(int n, int[][] roads) {
        List<int[]>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] r : roads) {
            graph[r[0]].add(new int[]{r[1], r[2]});
            graph[r[1]].add(new int[]{r[0], r[2]});
        }
        int MOD = (int)(1e9 + 7);
        long INF = (long) (Long.MAX_VALUE / 2 - 1e5);
        long[] dis = new long[n];
        boolean[] vis = new boolean[n];
        int[] cnt = new int[n];

        Arrays.fill(dis, INF);
        dis[0] = 0;
        cnt[0] = 1;


        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
        pq.add(new long[]{0, 0L});
        while (!pq.isEmpty()) {
            long[] t = pq.poll();
            int u = (int) t[0];
            if (vis[u]) {
                continue;
            }
            vis[u] = true;
            for (int[] p: graph[u]) {
                int v = p[0];
                long w = p[1];
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    // 新的最短路继承前驱的最短路径条数
                    cnt[v] = cnt[u];
                    pq.add(new long[]{v, dis[v]});
                }else if (dis[v] == dis[u] + w) {
                    // 相同的最短路走法需要进行累加并取模
                    cnt[v] = (cnt[v] + cnt[u]) % MOD;
                }
            }
        }
        return cnt[n - 1];
    }
}
